//
//  TreeNode.swift
//  构建二叉树 测试
//
//  Created by kys-20 on 2019/9/3.
//  Copyright © 2019 kys-20. All rights reserved.
//

import Foundation

public class TreeNode{
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val : Int){
        self.val = val
    }
}

struct createBTree {
    private var tree : TreeNode?
    mutating func insertValue(_ newElement: Int){
        if tree == nil{
            tree = TreeNode(newElement)
        }else{
            var p: TreeNode? = tree
            var q: TreeNode? = tree
            
            while p != nil{
                BstValue = p?.val
//                signal.wait()
                 if p!.val < newElement{
                    q = p
                    p = p!.right
                }else{
                    q = p
                    p = p!.left
                }
            }
            let temp = TreeNode(newElement)
            if q!.val < newElement{
                tapeWH = 1
                signalBST.wait()
                q!.right = temp
            }else{
                tapeWH = 0
                signalBST.wait()
                q!.left = temp
            }
            
        }
    }
    
    mutating func deleteValue(_ newElement: Int) {
        if tree != nil{
            var p : TreeNode? = tree
            var q : TreeNode? = tree
            
            while ( p != nil && p!.val != newElement ) {
                 if p!.val < newElement{
                      q = p
                      p = p!.right
                   }else{
                      q = p
                      p = p!.left
                   }
            }
            
            if p != nil {
//                q = p//找到要删除的根
                          if p!.left == nil && p!.right == nil{
                              let deleteValue = p!.val
                             q = nil
//                            tree = nil
                            
                            
                            BstValue = deleteValue
                            bstMoveType = BSTMoveType.deleteNoLeftNoRight
                            return
                          }
                          
                          if p!.left == nil && p!.right != nil{
                            let deleteValue = p!.right!.val
                               q = p?.right
                             BstValue = deleteValue
                            bstMoveType = BSTMoveType.deleteNoLeftHaveRight
                            return
                          }
                          
                          if q!.left != nil {
                               q = q!.left
                               while(q!.right != nil){
                                  q = q!.right
                               }
                            let deleteValue = q!.val //替换删除位置的值
                               p!.val = q!.val
                              while (p!.right != nil) {
                                  p = nil
                              }
                             BstValue = deleteValue
                            bstMoveType = BSTMoveType.deleteHaveLeftAndRight
                            return
                        }
            }else{
                 bstMoveType = BSTMoveType.deleteNoFind
                return
            }
        }else{
             bstMoveType = BSTMoveType.deleteNoFind
            return
        }
    }
                                             
    
    
    
    private var rootArray = [Int]()
    
    private mutating func preOrder(root: TreeNode?){
        if let root = root{
            rootArray.append(root.val)
            if root.left != nil{
                rootArray.append(root.left!.val)
            }else{
                rootArray.append(-1111)
            }
            if root.right != nil{
                rootArray.append(root.right!.val)
            }else{
                 rootArray.append(-1111)
            }
            preOrder(root: root.left)
            preOrder(root: root.right)
        }
    }
  
    private mutating func inOrder(root: TreeNode?){
        if let root = root{
            inOrder(root: root.left)
            
            rootArray.append(root.val)
            inOrder(root: root.right)
        }
    }
    private func postOrder(root: TreeNode?){
        if let root = root{
            postOrder(root: root.left)
            postOrder(root: root.right)
            print(root.val)
        }
    }
    

    //先序遍历二叉树
    mutating func perOrder() -> [Int]{
        rootArray.removeAll()
        print("先序遍历")
        preOrder(root: tree)
        print(rootArray)
        return rootArray
    }
    
    //中序遍历
   mutating func inOrder() -> [Int]{
    rootArray.removeAll()
        print("中序遍历")
        inOrder(root: tree)
        print(rootArray)
      return rootArray
    }
    //后序 遍历二叉树
    func postOrder(){
        print("后序遍历")
        postOrder(root: tree)
    }
    
 
    
    private func maxDepth(root: TreeNode?) -> Int{
        guard let root = root else{
            return 0
        }
        return max(maxDepth(root: root.left), maxDepth(root: root.left) + 1)
    }
    //返回树的最大深度
    func maxDepth() -> Int{
        return maxDepth(root: tree)
    }
 
}
